//
//  PSHashSet.m
//  PrefCore
//
//  Created by Sergey on 5/12/14.
//  Copyright (c) 2014 Play-on-smart. All rights reserved.
//

#import "PSHashSet.h"
#import "PSNode.h"

@interface PSHashSet () {

    PSNode *_buckets[PS_HASH_BUCKET_COUNT];

}

@end

static inline uint32_t IndexForHash(int h) {
    return h % PS_HASH_BUCKET_COUNT;
}

// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
static inline uint32_t ComputeHash(NSUInteger h) {
    h ^= (h >> 20) ^ (h >> 12);
    return (uint32_t)(h ^ (h >> 7) ^ (h >> 4));
}

@implementation PSHashSet

-(void)clear {
    for (int i = 0 ; i != PS_HASH_BUCKET_COUNT ; i++) {
        PSNode *n = _buckets[i];
        _buckets[i] = nil;
        while (n) {
            PSNode *tmp = n.nextInHashset;
            n.previousInHashset =
            n.nextInHashset = nil;
            n = tmp;
        }
    }
}

-(void)put:(PSNode*)node {
    uint32_t hash = ComputeHash([node hash]);
    node.bucketIndex = IndexForHash(hash);
    PSNode *head = _buckets[node.bucketIndex];
    if (head) {
        node.nextInHashset = head;
        head.previousInHashset = node;
    }
    _buckets[node.bucketIndex] = node;
}

-(PSNode*)get:(PSNode*)key {
    for (PSNode *node = _buckets[IndexForHash(ComputeHash([key hash]))] ; node ; node = node.nextInHashset) {
        if ([node isEqual:key]) {
            return node;
        }
    }
    return nil;
}

-(void)remove:(PSNode*)node {
    NSAssert(node.bucketIndex < PS_HASH_BUCKET_COUNT, @"Invalid node is presented for removal.");
    PSNode *head = _buckets[node.bucketIndex];
    PSNode *previous = node.previousInHashset;
    PSNode *next = node.nextInHashset;
    if (previous) {
        previous.nextInHashset = next;
    }
    if (next) {
        next.previousInHashset = previous;
    }
    if (head == node) {
        _buckets[node.bucketIndex] = next;
    }
    node.nextInHashset = nil;
    node.previousInHashset = nil;
    node.bucketIndex = PS_NO_HASH_BUCKET;
}

-(void)dealloc {
    [self clear];
}

@end
